package com.xizi.sort;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{5, 4, 3, 2, 1};
        System.out.println("排序前---------------------");
        System.out.println(Arrays.toString(arr));
        int n = arr.length;
        quickSort(arr, 0, n - 1);
        System.out.println("排序后---------------------");
        System.out.println(Arrays.toString(arr));
        //底层使用双轴快速排序
        Arrays.sort(arr);
    }

    //时间复杂度 O(NlogN)
    //1. 选取pivot
    //2. 划分，根据选取的pivot将数组划分成小于pivot的部分和大于pivot的部分
    //3. 递归求解小于pivot和大于pivot的部分
    public static void quickSort(int[] arr, int left, int right) {
        //边界判断 区间只剩下一个元素时直接返回
        if (left >= right) {
            return;
        }
        //取左边界为分界点
        int pivot = arr[left];
        //下面使用do while循环 i先减1 j加1
        int i = left - 1, j = right + 1;
        // 调整区间 使小于pivot的值在左边  大于pivot的值在右边
        // 当i==j相遇 arr[]就会被划分为两个区域
        while (i < j) {
            //从前往后找到第一次小于pivot的值
            do {
                i++;
            } while (arr[i] < pivot);
            //从后往前找到第一次大于pivot的值
            do {
                j--;
            } while (arr[j] > pivot);
            //然后进行交换
            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        //递归处理 左右区间
        quickSort(arr, left, j);
        quickSort(arr, j + 1, right);
    }

}
